int* path;         // step 0# 存放当前排列路径
int pathTop;       // step 0# path 的当前位置索引
int** ans;         // step 0# 存放所有合法排列结果
int ansTop;        // step 0# 当前结果数量

// step 1# 初始化 used 数组，将所有元素设为未使用（0）
void initialize(int* used, int usedLength) {
    for(int i = 0; i < usedLength; i++) {
        used[i] = 0;
    }
}

// step 2# 将当前 path 拷贝进结果 ans 中
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop);
    for(int i = 0; i < pathTop; i++) {
        tempPath[i] = path[i];
    }
    ans[ansTop++] = tempPath;
}

// step 3# 回溯函数，用于生成全排列
void backTracking(int* nums, int numsSize, int* used) {
    // step 3.1# 如果 path 长度等于数组长度，说明构造了一个合法排列
    if(pathTop == numsSize) {
        copy();
        return;
    }

    // step 3.2# 遍历所有可选数字
    for(int i = 0; i < numsSize; i++) {
        // note 1### 每一层中需要跳过已经使用过的元素
        // step 3.3# 如果该元素已被使用，跳过
        if(used[i])
            continue;

        // step 3.4# 做选择：标记使用并加入 path
        used[i] = 1;
        path[pathTop++] = nums[i];

        // step 3.5# 递归处理下一个位置
        backTracking(nums, numsSize, used);

        // step 3.6# 回溯：撤销选择
        pathTop--;
        used[i] = 0;
    }
}

// step 4# 主函数入口：生成 nums 的所有排列
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // step 4.1# 初始化辅助数组
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(sizeof(int*) * 1000); // 最多 n! 个排列
    int* used = (int*)malloc(sizeof(int) * numsSize);
    initialize(used, numsSize);
    ansTop = pathTop = 0;

    // step 4.2# 启动回溯
    backTracking(nums, numsSize, used);

    // step 4.3# 设置返回值
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    for(int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = numsSize; // 每个排列长度都是 numsSize
    }

    return ans; // step 4.4# 返回所有排列结果
}
